package net.tp.struct.adt;

import java.util.NoSuchElementException;

/**
 *
 * <p>Two-Stack Queue.</p>
 *
 * <p>Queue can be easily implemented using singly linked list. So why use 2 stack for queue? Because this implementation can utilize some properties of stack.</p>
 *
 * <p>With a stack, min value can be maintained and queried in constant time, so two-stack queue can maintain min value for query in constant time.</p>
 *
 * @author Trung Phan
 * @time $O(1)$ for enqueue and $O(1)$ amortized for dequeue operation.
 * @space $O(n)$
 *
 */
public class TwoStackQueue<E> {

    private SinglyNode<E> inputStack;
    private SinglyNode<E> outputStack;

    public void enqueue(E element) {
        inputStack = new SinglyNode<>(element, inputStack);
    }

    public E dequeue() {
        if (outputStack != null) {
            E result = outputStack.element;
            outputStack = outputStack.next;
            return result;
        }
        else if (inputStack != null) {
            while (inputStack != null) {
                SinglyNode<E> n = inputStack;
                inputStack = inputStack.next;
                n.next = outputStack;
                outputStack = n;
            }
            E result = outputStack.element;
            outputStack = outputStack.next;
            return result;
        }
        else {
            throw new NoSuchElementException();
        }
    }

    public boolean empty() {
        return inputStack == null && outputStack == null;
    }

}
